package SextaAula;

import java.util.TreeSet;

public class Grafo1Impl implements Grafo1{

	private ListaEncadeadaGrafo lista;
	
	public Grafo1Impl(){
		super();
	}

	@Override
	public boolean estahDirecionado() { 
		for(int i = 0; i < lista.numeroDeVertices(); i++){
			No atual = lista.getCabeca(i);
			while(atual.getProximo() != null){
				atual = atual.getProximo();
				if(!lista.existAresta(atual.getVertice(), i)){
					return true;
				}
			}
		}
		return false;
	}

	@Override
	public int grauInMaximo() {
		int max = 0;
		int total;
		for(int i = 0; i < lista.numeroDeVertices(); i++){
			total = 0;
			for(int j = 0; j < lista.numeroDeVertices(); j++){
				if(lista.existAresta(j, i)){
					total++;
				}
			}
			if(total > max){
				max = total;
			}
		}
		return max;
	}

	@Override
	public double grauInMedio() {
		int total = 0;
		for(int i = 0; i < lista.numeroDeVertices(); i++){
			for(int j = 0; j < lista.numeroDeVertices(); j++){
				if(lista.existAresta(j, i)){
					total++;
				}
			}
		}
		return total/lista.numeroDeVertices();
	}

	@Override
	public int grauInMinimo() {
		int min = lista.numeroDeVertices();
		int total;
		for(int i = 0; i < lista.numeroDeVertices(); i++){
			total = 0;
			for(int j = 0; j < lista.numeroDeVertices(); j++){
				if(lista.existAresta(j, i)){
					total++;
				}
			}
			if(total < min){
				min = total;
			}
		}
		return min;
	}

	@Override
	public double grauOutMedio() {
		int total = 0;
		for(int i = 0; i < numeroArestas(); i++){
			No no = lista.getCabeca(i);
			while(no.getProximo() != null){
				no = no.getProximo();
				total++;
			}
		}
		return total/lista.numeroDeVertices();
	}

	@Override
	public int numeroArestas() {
		TreeSet<String> set = new TreeSet<String>();
		No no;
		for(int i = 0; i < lista.numeroDeVertices(); i++){
			no = lista.getCabeca(i);
			while(no.getProximo() != null){
				if(i > no.getVertice()){
					set.add(no.getVertice() + i + "");
				}else{
					set.add(i + no.getVertice() + "");
				}
				no = no.getProximo();
			}
		}
		return set.size();
	}

	@Override
	public int numeroVertices() {
		return lista.numeroDeVertices();
	}

	@Override
	public void preencherGrafo(boolean[][] matriz, int tamanhoMatriz) {
		lista = new ListaEncadeadaGrafo(tamanhoMatriz);
		for(int i = 0; i < tamanhoMatriz; i++){
			for(int j = 0; j < tamanhoMatriz; j++){
				if(matriz[i][j]){
					lista.adicionarNo(i, new No(j));
				}
			}
		}
	}
	
	class No{
		private int vertice;
		private No proximo;
		
		public No(int vertice){
			this.vertice = vertice;
		}
		
		public int getVertice() {
			return vertice;
		}
		
		public No getProximo() {
			return proximo;
		}
		
		public void setProximo(No proximo) {
			this.proximo = proximo;
		}
	}
	
	class ListaEncadeadaGrafo{
		private No[] vertices;
		
		public ListaEncadeadaGrafo(int numeroVertices){
			vertices = new No[numeroVertices];
			for(int i = 0; i < numeroVertices; i++){
				vertices[i] = new No(i);
			}
		}
		
		public void adicionarNo(int vertice, No no){
			No atual = vertices[vertice];
			while(atual.getProximo() != null){
				atual = atual.getProximo();
			}
			atual.setProximo(no);
		}
		
		public No getCabeca(int vertice){
			return vertices[vertice];
		}
		
		public int numeroDeVertices(){
			return vertices.length;
		}
		
		public boolean existAresta(int i, int j){
			No no = getCabeca(i);
			while(no.getProximo() != null){
				no = no.getProximo();
				if(no.getVertice() == j){
					return true;
				}
			}
			return false;
		}
	}
}
